#ifndef __IM_HASH_H__
#define __IM_HASH_H__

#include <im_base_types.h>

/**
 * @defgroup IMHashTable
 * @ingroup PrivateIMBusIME
 * @{
 */

/**
 * @struct  IMHashTable
 * @brief   A generic hash table implementation.
 *
 * @struct  IMHashIterator
 * @brief   An iterator for a hash table.
 */

IM_BEGIN_DECLS

/**
 * @brief   Specifies the type of the hash function which is passed to
 *          im_hash_table_new() when an IMHashTable is created.
 *
 * The function is passed a key and should return an IMUInt hash value. The
 * functions im_direct_hash(), im_int_hash() and im_str_hash() provide hash
 * functions which can be used when the key is a IMPointer, IMInt, and IMChar*
 * respectively.
 *
 * @param   key     a key.
 *
 * @returns the hash value corresponding to the key.
 */
typedef IMUInt              (*IMHashFunc)       (IMConstPointer      key);

/**
 * @brief   Specifies the type of the function passed to
 *          im_hash_table_foreach_remove().
 *
 * It is called with each key/value pair, together with the user_data parameter
 * passed to im_hash_table_foreach_remove(). It should return TRUE if the
 * key/value pair should be removed from the IMHashTable.
 *
 * @param   key         a key.
 * @param   value       the value associated with the key.
 * @param   user_data   user data passed to im_hash_table_remove().
 *
 * @returns TRUE if the key/value pair should be removed from the IMHashTable.
 */
typedef IMBool              (*IMHRFunc)         (IMPointer           key,
                                                 IMPointer           value,
                                                 IMPointer           user_data);

/**
 * The IMHashTable struct is an opaque data structure to represent a Hash
 * Table.  It should only be accessed via the following functions.
 */
typedef struct _IMHashTable     IMHashTable;
/**
 * The IMHashIterator struct is an opaque data structure to represent a Hash
 * Table Iterator. It should only be accessed via the following functions.
 */
typedef struct _IMHashIterator  IMHashIterator;


/**
 * @brief   Creates a new IMHashTable.
 *
 * @param   hash_func   a function to create a hash value from a key. Hash
 *                      values are used to determine where keys are stored
 *                      within the IMHashTable data structure. The
 *                      im_direct_hash(), im_int_hash() and im_str_hash()
 *                      functions are provided for some common types of keys.
 *                      If hash_func is NULL, im_direct_hash() is used.
 * @param   key_equal_func  a function to check two keys for equality.
 *                      This is used when looking up keys in the IMHashTable.
 *                      The im_direct_equal(), im_int_equal() and
 *                      im_str_equal() functions are provided for the most
 *                      common types of keys. If key_equal_func is NULL, keys
 *                      are compared directly in a similar fashion to
 *                      im_direct_equal(), but without the overhead of a
 *                      function call.
 *
 * @returns a new IMHashTable.
 */
IMHashTable*    im_hash_table_new               (IMHashFunc          hash_func,
                                                 IMEqualFunc         key_equal_func);

/**
 * @brief   Creates a new IMHashTable like im_hash_table_new() and allows to
 *          specify functions to free the memory allocated for the key and
 *          value that get called when removing the entry from the IMHashTable.
 *
 * @param   hash_func           a function to create a hash value from a key.
 * @param   key_equal_func      a function to check two keys for equality.
 * @param   key_destroy_func    a function to free the memory allocated for the
 *                      key used when removing the entry from the IMHashTable
 *                      or NULL if you don't want to supply such a function.
 * @param   value_destroy_func  a function to free the memory allocated for the
 *                      value used when removing the entry from the IMHashTable
 *                      or NULL if you don't want to supply such a function.
 *
 * @returns a new IMHashTable.
 */
IMHashTable*    im_hash_table_new_full          (IMHashFunc          hash_func,
                                                 IMEqualFunc         key_equal_func,
                                                 IMDestroyFunc       key_destroy_func,
                                                 IMDestroyFunc       value_destroy_func);

/**
 * @brief   Destroys an IMHashTable and all keys and values in it.
 *
 * If keys and/or values are dynamically allocated, you should either free them
 * first or create the IMHashTable with destroy notifiers using
 * im_hash_table_new_full(). In the latter case the destroy functions you
 * supplied will be called on all keys and values during the destruction phase.
 *
 * @param   hash_table  the IMHashTable to be destroyed.
 */
void            im_hash_table_destroy           (IMHashTable        *hash_table);

/**
 * @brief   Inserts a new key and value into an IMHashTable.
 *
 * If the key already exists in the IMHashTable its current value is replaced
 * with the new value. If you supplied a value_destroy_func when creating the
 * IMHashTable, the old value is freed using that function. If you supplied a
 * key_destroy_func when creating the IMHashTable, the passed key is freed
 * using that function.
 *
 * @param   hash_table  an IMHashTable.
 * @param   key         a key to insert.
 * @param   value       the value to associate with the key.
 */
void            im_hash_table_insert            (IMHashTable        *hash_table,
                                                 IMPointer           key,
                                                 IMPointer           value);

/**
 * @brief   Inserts a new key and value into an IMHashTable similar to
 *          im_hash_table_insert().
 *
 * The difference is that if the key already exists in the IMHashTable, it gets
 * replaced by the new key.  If you supplied a key_destroy_func when creating
 * the IMHashTable, the old key is freed using that function.  If you supplied
 * a value_destroy_func when creating the IMHashTable, the old value is freed
 * using that function.
 *
 * @param   hash_table  an IMHashTable.
 * @param   key         a key to insert.
 * @param   value       the value to associate with the key.
 */
void            im_hash_table_replace           (IMHashTable        *hash_table,
                                                 IMPointer           key,
                                                 IMPointer           value);

/**
 * @brief   Removes a key and its associated value from an IMHashTable.
 *
 * If you supplied a key_destroy_func when creating the IMHashTable, the key is
 * freed using that function.  If you supplied a value_destroy_func when
 * creating the IMHashTable, the value is freed using that function.  Otherwise
 * you have to make sure that any dynamically allocated values are freed
 * yourself.
 *
 * @param   hash_table  an IMHashTable.
 * @param   key         the key to remove.
 *
 * @returns TRUE if the key was found and removed from the IMHashTable.
 */
IMBool          im_hash_table_remove            (IMHashTable        *hash_table,
                                                 IMConstPointer      key);

/**
 * @brief   Removes all keys and their associated values from an IMHashTable.
 *
 * If you supplied a key_destroy_func when creating the IMHashTable, the keys
 * are freed using that function.  If you supplied a value_destroy_func when
 * creating the IMHashTable, the values are freed using that function.
 * Otherwise you have to make sure that any dynamically allocated values are
 * freed yourself.
 *
 * @param   hash_table  an IMHashTable.
 */
void            im_hash_table_remove_all        (IMHashTable        *hash_table);

/**
 * @brief   Removes a key and its associated value from an IMHashTable without
 *          calling the key and value destroy functions.
 *
 * @param   hash_table  an IMHashTable.
 * @param   key         the key to remove.
 *
 * @returns TRUE if the key was found and removed from the IMHashTable.
 */
IMBool          im_hash_table_steal             (IMHashTable        *hash_table,
                                                 IMConstPointer      key);

/**
 * @brief   Removes all key and their associated values from an IMHashTable
 *          without calling the key and value destroy functions.
 *
 * @param   hash_table  an IMHashTable.
 */
void            im_hash_table_steal_all         (IMHashTable        *hash_table);

/**
 * @brief   Looks up a key in an IMHashTable.
 *
 * Note that this function cannot distinguish between a key that is not present
 * and one which is present and has the value NULL. If you need this
 * distinction, use im_hash_table_lookup_extended().
 *
 * @param   hash_table  an IMHashTable.
 * @param   key         the key to look up.
 *
 * @returns the associated value, or NULL if the key is not found.
 */
IMPointer       im_hash_table_lookup            (const IMHashTable  *hash_table,
                                                 IMConstPointer      key);

/**
 * @brief   Looks up a key in the IMHashTable.
 *
 * Unlike im_hash_table_lookup(), this function returns the original key, the
 * associated value, and TRUE if the key was found.  This is useful if you need
 * to free the memory allocated for the original key, for example before
 * calling im_hash_table_remove().
 *
 * @param   hash_table  an IMHashTable.
 * @param   key         the key to look up.
 * @param   orig_key    returns the original key.
 * @param   value       returns the value associated with the key.
 *
 * @returns TRUE if the key was found in the IMHashTable.
 */
IMBool          im_hash_table_lookup_extended   (const IMHashTable  *hash_table,
                                                 IMConstPointer      lookup_key,
                                                 IMPointer          *orig_key,
                                                 IMPointer          *value);
/**
 * @brief   Calls the given function for each of the key/value pairs in the
 *          IMHashTable.
 *
 * The function is passed the key and value of each pair, and the given
 * user_data parameter. The hash table may not be modified while iterating over
 * it (you can't add/remove items). To remove all items matching a predicate,
 * use im_hash_table_foreach_remove().
 *
 * See im_hash_table_find() for performance caveats for linear order searches
 * in contrast to im_hash_table_lookup().
 *
 * @param   hash_table  an IMHashTable.
 * @param   func        the function to call for each key/value pair.
 * @param   user_data   user data to pass to the function.
 *
 * @returns FALSE immediately if func returns FALSE.
 */
IMBool          im_hash_table_foreach           (const IMHashTable  *hash_table,
                                                 IMHRFunc            func,
                                                 IMPointer           user_data);

/**
 * @brief   Calls the given function for key/value pairs in the IMHashTable
 *          until predicate returns TRUE.
 *
 * The predicate function is passed the key and value of each pair, and the
 * given user_data parameter. The hash table may not be modified while
 * iterating over it (you can't add/remove items).
 *
 * Note that hash tables are really only optimized for forward lookups, i.e.
 * im_hash_table_lookup(). So code that frequently issues im_hash_table_find()
 * or im_hash_table_foreach() (e.g. in the order of once per every entry in a
 * hash table) should probably be reworked to use additional or different data
 * structures for reverse lookups (keep in mind that an O(n) find/foreach
 * operation issued for all n values in a hash table ends up needing O(n*n)
 * operations).
 *
 * @param   hash_table  an IMHashTable.
 * @param   predicate   function to test the key/value pairs for a certain
 *                      property.
 * @param   user_data   user data to pass to the function.
 *
 * @returns the value of the first key/value pair for which func evaluates to
 *          TRUE. If no pair with the requested property is found, NULL is
 *          returned.
 */
IMPointer       im_hash_table_find              (const IMHashTable  *hash_table,
                                                 IMHRFunc            predicate,
                                                 IMPointer           user_data);

/**
 * @brief   Calls the given function for each key/value pair in the IMHashTable.
 *
 * If func returns TRUE, then the key/value pair is removed from the
 * IMHashTable. If you supplied key or value destroy functions when creating
 * the IMHashTable, they are used to free the memory allocated for the removed
 * keys and values.
 *
 * @param   hash_table  an IMHashTable.
 * @param   func        the function to call for each key/value pair.
 * @param   user_data   user data to pass to the function.
 *
 * @returns the number of key/value pairs removed.
 */
IMUInt          im_hash_table_foreach_remove    (IMHashTable        *hash_table,
                                                 IMHRFunc            func,
                                                 IMPointer           user_data);

/**
 * @brief   Calls the given function for each key/value pair in the
 *          IMHashTable.
 *
 * If func returns TRUE, then the key/value pair is removed from the
 * IMHashTable, but no key or value destroy functions are called.
 *
 * @param   hash_table  an IMHashTable.
 * @param   func        the function to call for each key/value pair.
 * @param   user_data   user data to pass to the function.
 *
 * @returns the number of key/value pairs removed.
 */
IMUInt          im_hash_table_foreach_steal     (IMHashTable        *hash_table,
                                                 IMHRFunc            func,
                                                 IMPointer           user_data);

/**
 * @brief   Returns the number of elements contained in the IMHashTable.
 *
 * @param   hash_table  an IMHashTable.
 *
 * @returns the number of key/value pairs in the IMHashTable.
 */
IMUInt          im_hash_table_size              (const IMHashTable  *hash_table);

/**
 * @brief   Creates a new IMHashIterator for the IMHashTable.
 *
 * @param   hash_table  an IMHashTable.
 *
 * @returns a new IMHashIterator for the IMHashTable.
 */
IMHashIterator* im_hash_table_get_iterator      (IMHashTable        *hash_table);

/**
 * @brief   Destroys an IMHashIterator.
 *
 * @param   iterator    an IMHashIterator.
 */
void            im_hash_iterator_destroy        (IMHashIterator     *iterator);

/**
 * @brief   Compares two IMHashIterators.
 *
 * @param   iter1       an IMHashIterator.
 * @param   iter2       an IMHashIterator to compare with iter1.
 *
 * @returns TRUE if the two iterators match.
 */
IMBool          im_hash_iterator_equal          (const IMHashIterator *iter1,
                                                 const IMHashIterator *iter2);

/**
 * @brief   Iterates to the next key/value pair in the IMHashTable.
 *
 * @param   iterator    an IMHashIterator.
 *
 * @returns FALSE if there are no more key/value pairs to iterate to.
 */
IMBool          im_hash_iterator_next           (IMHashIterator     *iterator);

/**
 * @brief   Checks whether an IMHashIterator is correctly associated with an
 *          IMHashTable.
 *
 * @param   iterator    an IMHashIterator.
 *
 * @returns TRUE if iterator is a valid IMHashIterator.
 */
IMBool          im_hash_iterator_valid          (const IMHashIterator *iterator);

/**
 * @brief   Retrieves the key/value pair in the IMHashTable pointed to by the
 *          IMHashIterator.
 *
 * @param   iterator    an IMHashIterator.
 * @param   key         returns the key.
 * @param   value       returns the value associated with the key.
 *
 * @returns TRUE if iterator points to a valid key/value pair.
 */
IMBool          im_hash_iterator_get            (const IMHashIterator *iterator,
                                                 IMPointer          *key,
                                                 IMPointer          *value);
/**
 * @brief   Retrieves the key of the key/value pair in the IMHashTable pointed
 *          to by the IMHashIterator.
 *
 * @param   iterator    an IMHashIterator.
 *
 * @returns the key, or NULL if iterator is not valid.
 */
IMPointer       im_hash_iterator_get_key        (const IMHashIterator *iterator);

/**
 * @brief   Retrieves the value of the key/value pair in the IMHashTable
 *          pointed to by the IMHashIterator.
 *
 * @param   iterator    an IMHashIterator.
 *
 * @returns the value, or NULL if iterator is not valid.
 */
IMPointer       im_hash_iterator_get_value      (const IMHashIterator *iterator);

/**
 * @brief   Sets the value of the key/value pair in the IMHashTable pointed to
 *          by the IMHashIterator.
 *
 * If you supplied a value_destroy_func when creating the IMHashTable, the old
 * value is freed using that function.
 *
 * @param   iterator    an IMHashIterator.
 * @param   value       the new value.
 */
void            im_hash_iterator_set_value      (IMHashIterator     *iterator,
                                                 IMPointer           value);

/**
 * @brief   Removes a key/value pair in the IMHashTable pointed to by the
 *          IMHashIterator.
 *
 * If you supplied a key_destroy_func when creating the IMHashTable, the key is
 * freed using that function.  If you supplied a value_destroy_func when
 * creating the IMHashTable, the value is freed using that function.  Otherwise
 * you have to make sure that any dynamically allocated values are freed
 * yourself.
 *
 * @param   iterator    an IMHashIterator.
 *
 * @returns TRUE if iterator was valid and the referenced key/value pair
 *          removed from the IMHashTable.
 */
IMBool          im_hash_iterator_remove         (IMHashIterator     *iterator);

/**
 * @brief   Removes a key/value pair in the IMHashTable pointed to by the
 *          IMHashIterator without calling the key and value destroy functions.
 *
 * @param   iterator    an IMHashIterator.
 *
 * @returns TRUE if iterator was valid and the referenced key/value pair
 *          removed from the IMHashTable.
 */
IMBool          im_hash_iterator_steal          (IMHashIterator     *iterator);

/**
 * @brief   Compares two strings for byte-by-byte equality.
 *
 * It can be passed to im_hash_table_new() as the key_equal_func parameter,
 * when using strings as keys in an IMHashTable.
 *
 * @param   v1      a key.
 * @param   v2      a key to compare with v1.
 *
 * @returns TRUE if the two keys match.
 */
IMBool          im_str_equal                    (IMConstPointer      v1,
                                                 IMConstPointer      v2);

/**
 * @brief   Converts a string to a hash value.
 *
 * It can be passed to im_hash_table_new() as the hash_func parameter, when
 * using strings as keys in an IMHashTable.
 *
 * @param   v       a string key.
 *
 * @returns a hash value corresponding to the key.
 */
IMUInt          im_str_hash                     (IMConstPointer      v);

/**
 * @brief   Compares the two IMInt values being pointed to.
 *
 * It can be passed to im_hash_table_new() as the key_equal_func parameter,
 * when using pointers to integers as keys in an IMHashTable.
 *
 * @param   v1      a pointer to an IMInt key.
 * @param   v2      a pointer to an IMInt key to compare with v1.
 *
 * @returns TRUE if the two keys match.
 */
IMBool          im_int_equal                    (IMConstPointer      v1,
                                                 IMConstPointer      v2);

/**
 * @brief   Converts a pointer to an IMInt to a hash value.
 *
 * It can be passed to im_hash_table_new() as the hash_func parameter, when
 * using pointers to integers values as keys in an IMHashTable.
 *
 * @param   v       a pointer to an IMInt key.
 *
 * @returns a hash value corresponding to the key.
 */
IMUInt          im_int_hash                     (IMConstPointer      v);

/**
 * @brief   Converts an IMPointer to a hash value.
 *
 * It can be passed to im_hash_table_new() as the hash_func parameter, when
 * using pointers as keys in an IMHashTable.
 *
 * @param   v       an IMPointer key.
 *
 * @returns a hash value corresponding to the key.
 */
IMUInt          im_direct_hash                  (IMConstPointer      v);

/**
 * @brief   Compares the two IMPointer values being pointed to.
 *
 * It can be passed to im_hash_table_new() as the key_equal_func parameter,
 * when using pointers as keys in an IMHashTable.
 *
 * @param   v1      a key.
 * @param   v2      a key to compare with v1.
 *
 * @returns TRUE if the two keys match.
 */
IMBool          im_direct_equal                 (IMConstPointer      v1,
                                                 IMConstPointer      v2);

IM_END_DECLS
/** @} */

#endif
/*
vi:ts=4:nowrap:ai:expandtab
*/
